Katrina Ligett
In routing games, agents pick their routes through a network to minimize their own delay. A primary concern for the network designer in routing games is the average agent delay at equilibrium. A number of methods to control this average delay have received substantial attention, including network tolls, Stackelberg routing, and edge removal.
A related approach with arguably greater practical relevance, which has been studied in the transportation research literature but not so far in algorithmic game theory, is that of making investments in improvements to the edges of the network, so as to minimize (for a given investment budget) the average delay at equilibrium. In this paper, we study a model for this problem that is based on the transportation research literature, and present a number of tight results for polynomial-time algorithms. We first show that a simple algorithm that ignores equilibrium constraints is the best possible in general graphs with linear delay functions. To obtain better results, we then focus on more restricted graph topologies, and give polynomial-time algorithms for minimizing delay in a number of network topologies. In networks that consist of parallel links in series, however, we show that the problem is NP-hard to optimize. Despite this, we show that we can obtain a nearly optimal algorithm — i.e., we give an FPTAS — for series-parallel graphs.
To appear at IPCO 2014.
Joint work with Umang Bhaskar and Leonard Schulman.